import java.util.ArrayList;
import java.util.PriorityQueue;

/**
 * Created by L.jp
 * Description:给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
 * User: 86189
 * Date: 2022-04-08
 * Time: 9:40
 */
public class Main {
    //TopK问题使用小根堆或者大根堆可以解决海量数据的问题
    public static  ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        //有序的输出可以直接小根堆
        if(k==0){
            return new ArrayList<>();
        }
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        for (int i = 0; i < input.length; i++) {
            pq.add(input[i]);
        }
        ArrayList<Integer> list = new ArrayList<>();
        for(int j=0;j<k;j++){
            list.add(pq.poll());
        }
        return list;
    }
    
    public static void main(String[] args) {
        int[] input={4,5,1,6,2,7,3,8};
        int k=4;
        System.out.println(GetLeastNumbers_Solution(input, k));
    }
}
